package com.binarytree;

import java.util.HashMap;
import java.util.Map;

public class Solution19 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return getTree(nums, 0, nums.length);
    }

    public TreeNode getTree(int[] nums, int begin, int end) {
        if (begin >= end) return null;

        if (end - begin == 1) return new TreeNode(nums[begin]);

        int index = begin;
        int max = nums[index];
        for (int i = begin+1; i < end; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(nums[index]);
        root.left = getTree(nums,begin,index);
        root.right = getTree(nums,index+1,end);

        return root;

    }

}
